package dp;

/**
 * 切钢管问题
 */
public class CutRod {

    /**
     * 自顶向下
     *
     * @return
     */
    public static int topToDown(int[] p, int n) {
        if (n <= 0) {
            return 0;
        }
        // Max（Rk + R(n-k), p[n-1]
        int max = 0;
        for (int k = 1; k <= n; k++) {
            max = Math.max(p[k - 1] + topToDown(p, n - k), max);
        }
        return max;
    }

    /**
     * 自顶向下
     *
     * @return
     */
    public static int topToDown2(int[] p, int n) {
        if (n <= 0) {
            return 0;
        }
        // Max（Rk + R(n-k), p[n-1]
        int max = 0;
        for (int k = 1; k < n; k++) {
            max = Math.max(topToDown(p, k) + topToDown(p, n - k), max);
        }
        return Math.max(p[n - 1], max);
    }

    public static int downToTop(int[] p, int n) {
        int[] r = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int k = 0; k <= i; k++) {
                r[i] = Math.max(Math.max(r[k] + r[i - k], p[i - 1]), r[i]);
            }
        }
        return r[n];
    }

}
